import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 16.20. T9键盘
 * https://leetcode-cn.com/problems/t9-lcci/
 */
public class Solutions_mianshi_16_20 {
    public static void main(String[] args) {
//        String num = "8733";
//        String[] words = {"tree", "used"};  // output: {"tree", "used"}

        String num = "2";
        String[] words = {"a", "b", "c", "d"};  // output: {"a", "b", "c"}

        List<String> result = getValidT9Words(num, words);
        System.out.println(result);
    }

    public static int[] map = null;
    public static List<String> getValidT9Words(String num, String[] words) {
        // 建立哈希表，map[0] = 2 表示，字符 'a' 可以只能由按键 2 产生，map[13] = 6，表示字符 'n' 只能由按键 6 产生
        map = new int[]{2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6,
                6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};
        List<String> res = new ArrayList<>();
        for (String word : words) {
            if (check(num, word)) {
                res.add(word);
            }
        }
        return res;
    }

    /**
     * 判断相同索引下，num 上的字符是否可以产生 word 上的字符，即通过 map 表
     */
    public static boolean check(String num, String word) {
        for (int i = 0; i < word.length(); i++) {
            if (num.charAt(i) - '0' != map[word.charAt(i) - 'a']) {
                // num 按下的键，不能按出 word.charAt(i) 字符
                return false;
            }
        }
        return true;
    }
}
